package org.movee.jalgo.sort;

/**
 * 插入排序
 *
 * @author 54740559@qq.com
 * @version 1.0
 *
 */
public class InsertSort {

    public static int[] sort(int[] arr) {
        int len = arr.length;
        for (int i = 1; i < len; i++) {
            // 从位置i的前一位开始比较
            int curr = arr[i];
            // j是curr应该插入的位置
            int j = i;
            for (; j > 0 && curr < arr[j - 1]; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = curr;
        }

        return arr;

    }

}
